# 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
#
#  示例1:
#
#   输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
#  输出：true
#
#
#  示例2:
#
#   输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]],
#   start = 0, target = 4
#  输出 true
import collections
from typing import List


class Solution:
    def findWhetherExistsPath2(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        """
        解法二：邻接表 + dfs/bfs
        最优解为：邻接表 + dfs
        :param n:
        :param graph:
        :param start:
        :param target:
        :return:
        """
        def getAdjList() -> dict:
            adjList = collections.defaultdict(set)
            for node1, node2 in graph:
                adjList[node1].add(node2)
            print(adjList)
            return adjList

        def dfs(adjList: dict, startNode: int, targetNode: int, visited: List[bool]) -> bool:
            if startNode == targetNode:
                return True
            neighbours = adjList[startNode]
            for neighbour in neighbours:
                if not visited[neighbour]:
                    visited[neighbour] = True
                    if dfs(adjList, neighbour, targetNode, visited):
                        return True
            return False

        def bfs(adjList: dict, startNode: int, targetNode: int, visited: List[bool]) -> bool:
            queue = [startNode]
            while queue:
                tmp = queue[0]
                del queue[0]
                if not visited[tmp] and tmp == targetNode:
                    return True
                queue.extend(adjList[tmp])
            return False

        adjList = getAdjList()
        # return dfs(adjList, start, target, [False] * n)
        return bfs(adjList, start, target, [False] * n)

    def findWhetherExistsPath1(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        """
        解法一：邻接矩阵 + dfs
        :param n:
        :param graph:
        :param start:
        :param target:
        :return:
        """
        def getAdjMatrix() -> List[List[int]]:
            matrix = [[0] * n for i in range(n)]
            for node1, node2 in graph:
                matrix[node1][node2] = 1
            for line in matrix:
                print(line)
            return matrix

        def dfs(adjMatrix: List[List[int]], startNode: int, targetNode: int, visited: List[bool]) -> bool:
            if startNode == targetNode:
                return True
            for neighbour in range(n):
                if adjMatrix[startNode][neighbour] == 1 and not visited[neighbour]:
                    visited[neighbour] = True
                    if dfs(adjMatrix, neighbour, targetNode, visited):
                        return True
            return False

        adjMatrix = getAdjMatrix()
        return dfs(adjMatrix, start, target, [False] * n)

    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        return self.findWhetherExistsPath2(n, graph, start, target)


if __name__ == "__main__":
    n, graph = 5, [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]]
    start, target = 0, 4
    # n, graph = 3, [[0, 1], [0, 2], [1, 2], [1, 2]]
    # start, target = 0, 1
    print(Solution().findWhetherExistsPath(n, graph, start, target))
